{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Arithmetic Slices II - Subsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfArithmeticSlices"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #等差数列划分 II - 子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> ，返回 <code>nums</code> 中所有 <strong>等差子序列</strong> 的数目。</p>\n",
    "\n",
    "<p>如果一个序列中 <strong>至少有三个元素</strong> ，并且任意两个相邻元素之差相同，则称该序列为等差序列。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>[1, 3, 5, 7, 9]</code>、<code>[7, 7, 7, 7]</code> 和 <code>[3, -1, -5, -9]</code> 都是等差序列。</li>\n",
    "\t<li>再例如，<code>[1, 1, 2, 5, 7]</code> 不是等差序列。</li>\n",
    "</ul>\n",
    "\n",
    "<p>数组中的子序列是从数组中删除一些元素（也可能不删除）得到的一个序列。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，<code>[2,5,10]</code> 是 <code>[1,2,1,<em><strong>2</strong></em>,4,1,<strong><em>5</em></strong>,<em><strong>10</strong></em>]</code> 的一个子序列。</li>\n",
    "</ul>\n",
    "\n",
    "<p>题目数据保证答案是一个 <strong>32-bit</strong> 整数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,4,6,8,10]\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：</strong>所有的等差子序列为：\n",
    "[2,4,6]\n",
    "[4,6,8]\n",
    "[6,8,10]\n",
    "[2,4,6,8]\n",
    "[4,6,8,10]\n",
    "[2,4,6,8,10]\n",
    "[2,6,10]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [7,7,7,7,7]\n",
    "<strong>输出：</strong>16\n",
    "<strong>解释：</strong>数组中的任意子序列都是等差子序列。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1&nbsp; &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [arithmetic-slices-ii-subsequence](https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [arithmetic-slices-ii-subsequence](https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,4,6,8,10]', '[7,7,7,7,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        mp = defaultdict(list)\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            mp[nums[i]].append(i)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(2, n):\n",
    "            for j in range(1, i):\n",
    "                p = nums[j] * 2 - nums[i]\n",
    "                if p not in mp: continue\n",
    "                for k in mp[p]:\n",
    "                    if k >= j:\n",
    "                        break\n",
    "                    f[j][i] += f[k][j] + 1\n",
    "                ans += f[j][i]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "\n",
    "        loc = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            loc[nums[i]].append(i)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(2, n):\n",
    "            for j in range(1, i):\n",
    "                val = 2*nums[j] - nums[i]\n",
    "                if val in loc:\n",
    "                    for index in loc[val]:\n",
    "                        if index >= j:\n",
    "                            break\n",
    "                        dp[i][j] += dp[j][index] + 1\n",
    "                # if dp[i][j]>0:\n",
    "                #     print(i, j, dp[i][j])\n",
    "                res += dp[i][j]\n",
    "\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        mp = defaultdict(list) \n",
    "        for i, x in enumerate(nums):\n",
    "            mp[x].append(i)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(2, n):\n",
    "            for j in range(i - 1, 0, -1):\n",
    "                pre = 2 * nums[j] - nums[i] \n",
    "                if pre not in mp: continue\n",
    "                for k in mp[pre]:\n",
    "                    if k >= j:\n",
    "                        continue\n",
    "                    f[j][i] += f[k][j] + 1\n",
    "                ans += f[j][i]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "\n",
    "        loc = collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            loc[nums[i]].append(i)\n",
    "\n",
    "        res = 0\n",
    "        for i in range(2, n):\n",
    "            for j in range(1, i):\n",
    "                val = 2*nums[j] - nums[i]\n",
    "                if val in loc:\n",
    "                    for index in loc[val]:\n",
    "                        if index >= j:\n",
    "                            break\n",
    "                        dp[i][j] += dp[j][index] + 1\n",
    "                # if dp[i][j]>0:\n",
    "                #     print(i, j, dp[i][j])\n",
    "                res += dp[i][j]\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[2,4,6,8,10]\n",
    "[7,7,7,7,7]\n",
    "[0,2000000000,-294967296]\n",
    "[2147483647, -2147483647, 2147483647]\n",
    "[2147483638,2147483639,2147483640,2147483641,2147483642,2147483643,2147483644,2147483645,2147483646,2147483647,-2147483648,-2147483647,-2147483646,-2147483645,-2147483644,-2147483643,-2147483642,-2147483641,-2147483640,-2147483639]\n",
    "\n",
    "1 <= nums.length <= 1000\n",
    "-2^31 <= nums[i] <= 2^31 - 1\n",
    "\n",
    "Array, Dynamic Programming\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        mp = defaultdict(list)\n",
    "        n = len(nums)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            mp[nums[i-1]].append(i-1)\n",
    "            for j in range(i):\n",
    "                t = 2*nums[j]-nums[i]\n",
    "                if t not in mp: continue\n",
    "                for d in mp[t]:\n",
    "                    if d < j:\n",
    "                        dp[j][i] += dp[d][j] + 1\n",
    "                res += dp[j][i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        f = [Counter() for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            cnt1 = f[i]\n",
    "            for j in range(i):\n",
    "                d = nums[i] - nums[j]\n",
    "                cnt1[d] += 1 + f[j][d]\n",
    "                ans += 1 + f[j][d]    \n",
    "        \n",
    "        return ans - (n - 1) * n // 2\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [{} for _ in range(n)]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                dif = nums[i] - nums[j]\n",
    "                dp[i][dif] = dp[i].get(dif, 0) + dp[j].get(dif, 0) + 1\n",
    "                if dif in dp[j]:\n",
    "                    res += dp[j][dif]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        dp[i]是前i个元素子序列情况，dp[i]内是一个hash表，表中键为d是子序列差值 值是cnt是这个差值下的数量\n",
    "        如何保证长度为3的个数 用总的减去长度为2的子序列个数 长度为2的子序列个数就是任何两个数的组合\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        dp = [{} for _ in range(n)]\n",
    "        rs = 0\n",
    "        for i in range(n):\n",
    "            dic = {}\n",
    "            for j in range(i):\n",
    "                diff = nums[i]-nums[j] #差值\n",
    "                cnt = dp[j].get(diff,0) #以j结尾差值为diff的个数\n",
    "                dp[i][diff] = dp[i].get(diff,0)+cnt+1 #累积之前的 加上前面元素的 再加1\n",
    "        for dic in dp:\n",
    "            for k,v in dic.items():\n",
    "                rs += v\n",
    "        return rs-(0+n-1)*n//2 \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        dp=defaultdict(dict)\n",
    "        for i in range(n):\n",
    "            for j in range(i-1,-1,-1):\n",
    "                d=nums[i]-nums[j]\n",
    "                cnt=dp[i].get(d,0)\n",
    "                cnt+=dp[j].get(d,0)\n",
    "                cnt+=1\n",
    "                dp[i][d]=cnt\n",
    "        ans=0\n",
    "        for j in range(n-1,-1,-1):\n",
    "            for k in dp[j].values():\n",
    "                    ans+=k\n",
    "        s=(n)*(n-1)//2\n",
    "        return ans-s\n",
    "                    \n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        map_list = [{}] * n\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            map = {}\n",
    "            for j in range(0, i):\n",
    "                diff = nums[i] - nums[j]\n",
    "                map[diff] = (map[diff] if diff in map else 0) + (map_list[j][diff] if diff in map_list[j] else 0) + 1\n",
    "                ans += map_list[j][diff] if diff in map_list[j] else 0\n",
    "            map_list[i] = map\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        dp = [{} for _ in range(len(nums))]\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i):\n",
    "                d = nums[i]-nums[j]\n",
    "                if d not in dp[i]:\n",
    "                    dp[i][d] = 0\n",
    "                if d in dp[j]:\n",
    "                    dp[i][d] += dp[j][d] + 1\n",
    "                else:\n",
    "                    dp[i][d] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            for d in dp[i]:\n",
    "                ans += dp[i][d]\n",
    "        ans -= len(nums) * (len(nums)-1) / 2\n",
    "        return int(ans)\n",
    "        \n",
    "            \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        slieceCount = 0\n",
    "\n",
    "        # m的范围很大，无法使用数组下标表示，因此需要维护长度为n的哈希表数组dp\n",
    "        # dp[i]表示以nums[i]结尾的每一种公差的等差子序列的个数\n",
    "        ans = 0\n",
    "        dp = [{} for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i-1,-1,-1):\n",
    "                diff = nums[i]-nums[j]\n",
    "                prevCount = dp[j].get(diff,0)\n",
    "                slieceCount += prevCount\n",
    "                curCout = dp[i].get(diff,0)\n",
    "                dp[i][diff] = prevCount+curCout+1\n",
    "        return slieceCount\n",
    "        \n",
    "\n",
    "\n",
    "        # dp = [[0]*m for _ in range(n)]\n",
    "        # for end in range(1,n):\n",
    "        #     for start in range(0,end):\n",
    "        #         for diff in range(m):\n",
    "        #             dp[end][diff] = dp[start][diff]+1\n",
    "        \n",
    "        # ans  = 0\n",
    "        # for diff in range(m):\n",
    "        #     ans += dp[n-1][diff]\n",
    "        # return ans\n",
    "\n",
    "'''\n",
    "dp[i][j]表示以i结尾，j为差的子序列个数\n",
    "dp[i][j] = dp[k][j]+1         if (nums[i]-nums[k] == j)\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        # 最长递增子序列\n",
    "        dfs[i] = max(dfs[j]) + 1 j<i and n[j] < n[i]\n",
    "        --\n",
    "        f[i] = max(f[j]) + 1 j < i and n[j] < n[i]\n",
    "\n",
    "        # 本题：n[i]在n[j]的基础上构成等差\n",
    "        dfs(i, diff) = max(dfs(j, diff)) + 1\n",
    "        f[i][diff] = max(f[j][diff]) + 1\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        dp = [{} for _ in range(n)]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                dif = nums[i] - nums[j]\n",
    "                dp[i][dif] = dp[i].get(dif, 0) + dp[j].get(dif, 0) + 1\n",
    "                if dif in dp[j]:\n",
    "                    res += dp[j][dif]\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        # 最长递增子序列\n",
    "        dfs[i] = max(dfs[j]) + 1 j<i and n[j] < n[i]\n",
    "        --\n",
    "        f[i] = max(f[j]) + 1 j < i and n[j] < n[i]\n",
    "\n",
    "        # 本题：n[i]在n[j]的基础上构成等差\n",
    "        dfs(i, diff) = max(dfs(j, diff)) + 1\n",
    "        f[i][diff] = max(f[j][diff]) + 1\n",
    " 2    4      6             8                   10\n",
    "[{}, {2: 1}, {},           {},                 {}]\n",
    "[{}, {2: 1}, {4: 1},       {},                 {}]\n",
    "[{}, {2: 1}, {4: 1, 2: 2}, {},                 {}]\n",
    "[{}, {2: 1}, {4: 1, 2: 2}, {6: 1},             {}]\n",
    "[{}, {2: 1}, {4: 1, 2: 2}, {6: 1, 4: 1},       {}]\n",
    "[{}, {2: 1}, {4: 1, 2: 2}, {6: 1, 4: 1, 2: 3}, {}]\n",
    "[{}, {2: 1}, {4: 1, 2: 2}, {6: 1, 4: 1, 2: 3}, {8: 1}]\n",
    "[{}, {2: 1}, {4: 1, 2: 2}, {6: 1, 4: 1, 2: 3}, {8: 1, 6: 1}]\n",
    "[{}, {2: 1}, {4: 1, 2: 2}, {6: 1, 4: 1, 2: 3}, {8: 1, 6: 1, 4: 2}]\n",
    "[{}, {2: 1}, {4: 1, 2: 2}, {6: 1, 4: 1, 2: 3}, {8: 1, 6: 1, 4: 2, 2: 4}]\n",
    "字典[0]:公差\n",
    "字典[1]:以i结尾的等差数列，如果公差为字典[i],前面有字典[1]个数\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        dp = [{} for _ in range(n)]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                dif = nums[i] - nums[j]\n",
    "                dp[i][dif] = dp[i].get(dif, 0) + dp[j].get(dif, 0) + 1\n",
    "                # 状态值里有同样的 diff 的 -- 可以构成长度>=3的等差数列\n",
    "                if dif in dp[j]:\n",
    "                    res += dp[j][dif]\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [Counter() for i in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1,n):\n",
    "                dif = nums[j]-nums[i]\n",
    "                dp[j][dif] += dp[i][dif] + 1\n",
    "                ans += dp[i][dif]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [Counter() for _ in range(n)]\n",
    "        rst = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                k = nums[i] - nums[j]\n",
    "                dp[i][k] += dp[j][k] + 1\n",
    "        for i in range(1, n):\n",
    "            for k, v in dp[i].items():\n",
    "                rst += v\n",
    "        rst -= n * (n - 1) // 2\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef numberOfArithmeticSlices(self, A):\n",
    "\t\tn, ans = len(A), 0\n",
    "\t\tdp = [defaultdict(int) for _ in range(n)]\n",
    "\t\tfor i in range(n):\n",
    "\t\t\tfor j in range(i):\n",
    "\t\t\t\td = A[i] - A[j]\n",
    "\t\t\t\tdp[i][d] += 1\n",
    "\t\t\t\tif d in dp[j]:\n",
    "\t\t\t\t\tdp[i][d] += dp[j][d]\n",
    "\t\t\t\t\tans += dp[j][d]\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        #思路就是dfs(i,j)表示以i数组元素结尾并以j为等差的序列个数\n",
    "        #转移方程dfs(i,j)=sum(dfs(k,j)+1)其中(0=<k<i)\n",
    "        #如果说j以数组中max-min为范围的话，内存会爆，因为2^32~=10^9,则用存在的等差项个数代替，也就引入了哈希表，即dp=[{},{},{}....,{},{}]的形式出现\n",
    "        #但是统计的过程中的\n",
    "        n=len(nums)\n",
    "        dp=defaultdict(dict)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            for j in range(i-1,-1,-1):\n",
    "                d=nums[i]-nums[j]\n",
    "                cnt=dp[i].get(d,0)\n",
    "                cnt+=dp[j].get(d,0)\n",
    "                cnt+=1\n",
    "                dp[i][d]=cnt\n",
    "            ans+=sum(dp[i].values())\n",
    "        \n",
    "        s=(n)*(n-1)//2\n",
    "        return ans-s\n",
    "                    \n",
    "                \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        dp = [{} for i in range(len(nums))]\n",
    "        res = 0\n",
    "        for i in range(len(nums)-1):\n",
    "            for j in range(i+1, len(nums)):\n",
    "                key = nums[j] - nums[i]\n",
    "                if key not in dp[j]:\n",
    "                    dp[j][key] = 0\n",
    "                if key in dp[i]:\n",
    "                    res += dp[i][key]\n",
    "                    dp[j][key] += dp[i][key] + 1\n",
    "                else:\n",
    "                    dp[j][key] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        dic = collections.defaultdict(lambda: collections.Counter())\n",
    "        for i in range(1, n):\n",
    "            for j in range(i - 1, - 1, - 1):\n",
    "                diff = nums[i] - nums[j]\n",
    "                res += dic[j][diff]\n",
    "                dic[i][diff] += dic[j][diff] + 1 \n",
    "        return res \n",
    "\n",
    "\n",
    "        n = len(nums)\n",
    "        dic = [collections.Counter() for _ in range(n)]\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i - 1, - 1, - 1):\n",
    "                diff = nums[i] - nums[j]\n",
    "                res += dic[j][diff]\n",
    "                dic[i][diff] += dic[j][diff] + 1 \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [Counter() for i in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                dif = nums[j]-nums[i]\n",
    "                dp[j][dif] += dp[i][dif] + 1\n",
    "                ans += dp[i][dif]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        # 用dp[i][j] 记录 以nums[i] 为结尾公差为j的子序列个数\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return 0\n",
    "        dp = [Counter() for _ in range(n)]\n",
    "        r = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                d = nums[i] - nums[j]\n",
    "                dp[i][d] += 1\n",
    "                if dp[j][d]:\n",
    "                    r += dp[j][d]\n",
    "                    dp[i][d] += dp[j][d]\n",
    "        return r\n",
    "\n",
    "\n",
    "\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        # 分析，每三个数构成一个等差序列，那么从第一个数出发，和第二个数的差，要找到后面有没有等于第二个数加这个差的\n",
    "        # 比如[2, 4, 6, 6, 6]中，2,4分别和3个6均可以构成一个答案\n",
    "        # 固定前面的部分，我们要知道我们要找的val，以及val对应的前面的等差序列个数\n",
    "        \n",
    "        n, ans = len(nums), 0\n",
    "        dp = [Counter() for _ in range(n)]\n",
    "        # 目前某等差数列的末尾值(也有可能是只有它自己)\n",
    "        for i in range(n-1):\n",
    "            # 加入这个值，能和这个末尾值的哪个等差序列构成等差序列吗？\n",
    "            for j in range(i + 1, n):\n",
    "                # 当前的差，用来比对和i构成的等差数列\n",
    "                diff = nums[j] - nums[i]\n",
    "                # 如果前面这个末尾有以diff为差的等差序列，那么j可以成为新的末尾，个数是它的个数加1, 多了个[i,j]等差序列！\n",
    "                # 如果前面这个末尾没有以diff为差的等差序列，那么j和i构成一个等差序列的起始两位，个数为(0+1), 后面有和j差为diff的话，就可以构成等差序列了\n",
    "                dp[j][diff] += dp[i][diff] + 1\n",
    "                # i, j以及i前面的以diff为公差的等差序列，可以构成这么多新的等差序列\n",
    "                # 这里和昨天的题一致, [i] 和 [j] 能构成等差序列只有当 [i] 有以 diff 为差的等差序列时 (至少两个数，因为加上j至少三个)\n",
    "                ans += dp[i][diff]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        # dp[i][d] = dp[j][d] + 1 ..... nums[i] - nums[j] == d\n",
    "        dp = [defaultdict(int) for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                d = nums[i] - nums[j]\n",
    "                ans += dp[j][d]\n",
    "                dp[i][d] += dp[j][d] + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        f = [defaultdict(int) for _ in nums]\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                d = x - nums[j]\n",
    "                cnt = f[j][d]\n",
    "                ans += cnt\n",
    "                f[i][d] += cnt + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        d = [defaultdict(int) for _ in range(n)]\n",
    "        ans = 0\n",
    "        for j in range(n):\n",
    "            for i in range(j):\n",
    "                diff = nums[j] - nums[i]\n",
    "                ans += d[i][diff]\n",
    "                d[j][diff] += d[i][diff] + 1\n",
    "            # print(j, d[j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        f = [defaultdict(int) for _ in nums]\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                d = x - nums[j]\n",
    "                cnt = f[j][d]\n",
    "                ans += cnt\n",
    "                f[i][d] += cnt + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        # n = len(nums)\n",
    "        # ans = 0\n",
    "        # @cache\n",
    "        # def dfs(i):\n",
    "        #     d = defaultdict(int)\n",
    "        #     for j in range(i): # 枚举选哪个\n",
    "        #         diff = nums[i] - nums[j]\n",
    "        #         d0 = dfs(j)\n",
    "        #         nonlocal ans\n",
    "        #         ans += d0[diff]\n",
    "        #         d[diff] += d0[diff] + 1\n",
    "        #     return d\n",
    "        # dfs(n-1)\n",
    "        # return ans\n",
    "\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        f = [defaultdict(int) for _ in range(n)] # f[i][d]表示选定以nums[i]结尾, 公差为d的且长度>=2的等差序列的数量\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(i): # 枚举选哪个\n",
    "                diff = x - nums[j]\n",
    "                cnt = f[j][diff]\n",
    "                ans += cnt # 加上nums[i]能组成长度>=3的子序列\n",
    "                f[i][diff] += cnt + 1 # 例如序列0,2,4,6  diff=2时，f的值分别为0,1,2,3\n",
    "        # for x in f:\n",
    "        #    print(x)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        dp = [collections.defaultdict(int) for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                d = nums[i] - nums[j]\n",
    "                c = dp[j][d]\n",
    "                dp[i][d] += c + 1\n",
    "                ans += c\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\" \n",
    "    该题目与第 I 题目的区别在于等差数列中的元素在原始数组中不一定连续\n",
    "    \n",
    "    定义 dp[i][d] 表示以 i 结尾，以 d 为公差的子序列数目\n",
    "        dp[i][d] += dp[j][d] + 1, j in [0, i-1]\n",
    "        nums[i] - nums[j] = d\n",
    "\n",
    "    TIPS: 由于 d 的取值可能不同，因此其使用哈希表来实现\n",
    "\n",
    " \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [defaultdict(int) for _ in range(n)]\n",
    "\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                d = nums[i] - nums[j]\n",
    "                dp[i][d] += dp[j][d] + 1\n",
    "                result += dp[j][d]\n",
    "        return result \n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [defaultdict(int) for _ in range(n)]\n",
    "\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                d = nums[i] - nums[j]\n",
    "                dp[i][d] += dp[j][d] + 1\n",
    "            result += sum(dp[i].values())\n",
    "        return result - (n * (n-1))//2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        \n",
    "        ans = 0\n",
    "        f = [defaultdict(int) for _ in nums]\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                d = x - nums[j]\n",
    "                cnt = f[j][d]\n",
    "                ans += cnt\n",
    "                f[i][d] += cnt + 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        f = [defaultdict(int) for _ in nums]\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                d = x - nums[j]\n",
    "                cnt = f[j][d]\n",
    "                ans += cnt\n",
    "                f[i][d] += cnt + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        f = [defaultdict(int) for _ in nums]\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                d = x - nums[j]\n",
    "                cnt = f[j][d]\n",
    "                ans += cnt\n",
    "                f[i][d] += cnt + 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        dp = [defaultdict(int) for _ in range(len(nums))] \n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i):\n",
    "                diff = nums[i] - nums[j]\n",
    "                dp[i][diff] += dp[j][diff] +  1\n",
    "                # 说明满足长度大于等于3\n",
    "                if diff in dp[j]:\n",
    "                    res += dp[j][diff]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        f = [collections.defaultdict(int) for _ in nums] ### 给每一个数字建立了一个哈嘻列表\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                d = x - nums[j]\n",
    "                cnt = f[j][d] ### [d]应该是字典的key了\n",
    "                ans += cnt #### 这个必须在前面，因为是弱等差序列\n",
    "                f[i][d] += cnt + 1 ### d本来就是\n",
    "        return ans\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "\n",
    "        # dp[i][d] 表示尾项为 nums[i] 公差为 d 的等差子序列的个数\n",
    "        dp = [defaultdict(int) for _ in range(n)]\n",
    "\n",
    "        # 遍历 nums[i] 和 nums[j]，分别作为等差数列的最后 1/2 项。\n",
    "        for i, num in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                # 公差为 d\n",
    "                d = num - nums[j]\n",
    "\n",
    "                # 以 nums[j] 结尾，公差为 d 的等差数列有 cnt 个\n",
    "                cnt = dp[j][d]\n",
    "\n",
    "                # 总的等差数列数目加 1\n",
    "                res += cnt\n",
    "\n",
    "                # 以 nums[i] 结尾，公差为 d 的等差数列有 cnt + 1 个\n",
    "                # 比 dp[j][d] 多了一个 (nums[j], nums[i])\n",
    "                dp[i][d] += cnt + 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [defaultdict(int) for i in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                d = nums[i]-nums[j]\n",
    "                ans += f[j][d]\n",
    "                f[i][d] += f[j][d]+1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        f = [defaultdict(int) for _ in nums]\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                d = x - nums[j]\n",
    "                cnt = f[j][d]\n",
    "                ans += cnt\n",
    "                f[i][d] += cnt + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [defaultdict(int) for _ in nums]\n",
    "\n",
    "        if n <= 2:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                gap = nums[i] - nums[j]\n",
    "                cnt = dp[j][gap]\n",
    "                ans += cnt\n",
    "                dp[i][gap] += cnt + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        等差子序列，序列DP问题\n",
    "        f[i][j]代表以nums[i]为结尾，差值为j的子序列个数\n",
    "        f[i][d]=sum([f[j][d] + 1 for j in range(i)]\n",
    "        使用哈希表充当集合，f[i]为一个哈希表，哈希表以{d:cnt},d为差值，cnt为子序列数量\n",
    "        减去长度为2的子序列的个数，从ans中减去\n",
    "        '''\n",
    "        n, res = len(nums), 0\n",
    "        dp = [defaultdict(int) for _ in range(n)]\n",
    "        for i, num in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                d = num - nums[j]\n",
    "                dp[i][d] += dp[j][d] + 1\n",
    "        res += sum(sum([v for _, v in dic.items()]) for dic in dp)\n",
    "        res -= n * (n-1) // 2 \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        import collections\n",
    "        n = len(nums)\n",
    "        dp = [collections.defaultdict(int) for i in range(n)]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                diff = nums[i] - nums[j]\n",
    "                dp[i][diff] += dp[j][diff] + 1\n",
    "                if dp[j][diff]:\n",
    "                    res += dp[j][diff]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        max_d = max(nums) - min(nums)\n",
    "\n",
    "        # f = [[0] * (max_d * 2 + 1) for _ in range(n)]\n",
    "        # f = [[0] * (n) for _ in range(max_d * 2 + 1)]\n",
    "        f = []\n",
    "\n",
    "        for i in range(n):\n",
    "            cur = collections.defaultdict(int)\n",
    "            for j in range(i):\n",
    "                d = nums[i] - nums[j]\n",
    "                cnt = cur[d]\n",
    "                cnt += f[j][d] + 1\n",
    "                cur[d] = cnt\n",
    "            f.append(cur)\n",
    "        # print(f)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            curdt = f[i]\n",
    "            for ks in curdt.keys():\n",
    "                res += curdt[ks]\n",
    "        # print(res)\n",
    "\n",
    "        return int(res - ((n-1) * n / 2))\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\" \n",
    "    该题目与第 I 题目的区别在于等差数列中的元素在原始数组中不一定连续\n",
    "    \n",
    "    定义 dp[i][d] 表示以 i 结尾，以 d 为公差的子序列数目\n",
    "        dp[i][d] += dp[j][d] + 1, j in [0, i-1]\n",
    "        nums[i] - nums[j] = d\n",
    "\n",
    "    TIPS: 由于 d 的取值可能不同，因此其使用哈希表来实现\n",
    "\n",
    " \"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [defaultdict(int) for _ in range(n)]\n",
    "\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                d = nums[i] - nums[j]\n",
    "                dp[i][d] += dp[j][d] + 1\n",
    "                result += dp[j][d]\n",
    "        return result \n",
    "\n",
    "\"\"\" \n",
    "    假设数组的前三项为\n",
    "     a -> b -> c,\n",
    "     则依据下面的算法: dp_a = 0, dp_b = 1, dp_c = 2, 实际上考虑的是任意两个元素组成的数列,\n",
    "     result 统计的结果包含 2 个元素的数列和 2 个元素以上的数列, 因此需要将 2 个元素的数列个数减去,\n",
    "     长度为 n 的数组, 包含 2 个元素的数列个数为 n * (n-1) / 2\n",
    "\n",
    " \"\"\"\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [defaultdict(int) for _ in range(n)]\n",
    "\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                d = nums[i] - nums[j]\n",
    "                dp[i][d] += dp[j][d] + 1\n",
    "            result += sum(dp[i].values())\n",
    "        return result - (n * (n-1))//2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        max_d = max(nums) - min(nums)\n",
    "\n",
    "        # f = [[0] * (max_d * 2 + 1) for _ in range(n)]\n",
    "        # f = [[0] * (n) for _ in range(max_d * 2 + 1)]\n",
    "        f = []\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     cur = collections.defaultdict(int)\n",
    "        #     for j in range(i):\n",
    "        #         d = nums[i] - nums[j]\n",
    "        #         cnt = cur[d]\n",
    "        #         cnt += f[j][d] + 1\n",
    "        #         cur[d] = cnt\n",
    "        #     f.append(cur)\n",
    "        # # print(f)\n",
    "        # res = 0\n",
    "        # for i in range(n):\n",
    "        #     curdt = f[i]\n",
    "        #     for ks in curdt.keys():\n",
    "        #         res += curdt[ks]\n",
    "        # # print(res)\n",
    "\n",
    "        # return int(res - ((n-1) * n / 2))\n",
    "\n",
    "\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            cur = collections.defaultdict(int)\n",
    "            for j in range(i):\n",
    "                d = nums[i] - nums[j]\n",
    "                if f[j][d] > 0:\n",
    "                    res += f[j][d]\n",
    "                    cur[d] += f[j][d]\n",
    "                # cnt = cur[d]\n",
    "                # cnt += f[j][d] + 1\n",
    "                # cur[d] = cnt\n",
    "                cur[d] += 1\n",
    "            f.append(cur)\n",
    "        return int(res)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        序列dp类\n",
    "        dp[i] 需要记录 nums[i] 结尾的所有等差子序列\n",
    "        dp[i][delta] 表示 nums[i-1] 结尾，差为 delta 的等差数列个数\n",
    "        最后遍历一遍dp结果即可\n",
    "\n",
    "        \"\"\"\n",
    "        ret = 0\n",
    "        dp = [defaultdict(int) for i in range(len(nums)+1)]\n",
    "        for i in range(len(nums)+1):\n",
    "            if i == 0:\n",
    "                continue\n",
    "            for j in range(1, i):\n",
    "                delta = nums[i-1] - nums[j-1]\n",
    "                # dp[j][delta] 不能构成等差数列的时候，ret加的是0\n",
    "                # 前面至少有两个数字 ret 才会加东西，包括当前数那么就至少有三个数了\n",
    "                ret += dp[j][delta]\n",
    "                dp[i][delta] += dp[j][delta] + 1\n",
    "        # 这样不对，有重复数字无法判断，比如 [2,2,3,4]\n",
    "        # for ele in dp:\n",
    "        #     for k, v in ele.items():\n",
    "        #         if v >= 3:\n",
    "        #             if k != 0:\n",
    "        #                 ret += v-3+1\n",
    "        #             else:\n",
    "        #                 ret += 2**(v-1)-(1+v-1)\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # f[i][d] 表示尾项为 nums[i]，公差为 d 的弱等差子序列的个数。\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        f = [defaultdict(int) for _ in nums]\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                d = x - nums[j]\n",
    "                cnt = f[j][d]\n",
    "                ans += cnt\n",
    "                f[i][d] += cnt + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        f = [defaultdict(int) for _ in nums]\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                d = x - nums[j]\n",
    "                cnt = f[j][d]\n",
    "                ans += cnt\n",
    "                f[i][d] += cnt + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        f = [defaultdict(int) for _ in nums]\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                d = x - nums[j]\n",
    "                cnt = f[j][d]\n",
    "                ans += cnt\n",
    "                f[i][d] += cnt + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [defaultdict(int) for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                d = nums[i] - nums[j]\n",
    "                cnt = dp[j][d]\n",
    "                \"\"\"\n",
    "                为啥要+1，多出来的这个1是哪一对？\n",
    "                比如2 4 6 8，此时nums[i] = 10，\n",
    "                那么求dp[nums=10][2]时，之前的dp[nums=8][2]的那些对后面，都带上10，这些的数量就是cnt。\n",
    "\n",
    "                多出来的一对是8、10这一对！！！\n",
    "                \"\"\"\n",
    "                ans += cnt + 1\n",
    "                dp[i][d] += cnt + 1\n",
    "\n",
    "        return ans - n * (n - 1) // 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        f = [defaultdict(int) for _ in nums]\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                d = x - nums[j]\n",
    "                cnt = f[j][d]\n",
    "                ans += cnt\n",
    "                f[i][d] += cnt + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        dp = [defaultdict(int) for _ in range(len(nums))] \n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i):\n",
    "                diff = nums[i] - nums[j]\n",
    "                dp[i][diff] += dp[j][diff] +  1\n",
    "                # 说明满足长度大于等于3\n",
    "                if diff in dp[j]:\n",
    "                    res += dp[j][diff]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        size = len(nums)\n",
    "        if size < 3: return 0\n",
    "        dp = [defaultdict(int) for _  in range(size)]\n",
    "        res = 0\n",
    "        for i in range(size):\n",
    "            for j in range(i):\n",
    "                diff = nums[i] - nums[j]\n",
    "                dp[i][diff] += dp[j][diff] + 1\n",
    "                if diff in dp[j]:\n",
    "                    res += dp[j][diff]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        if len(nums) < 3:\n",
    "            return 0\n",
    "        # dp[i][d] nums[i]结尾公差为d的等差子序列的个数\n",
    "        dp = [collections.defaultdict(int) for _ in range(len(nums))]\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i):\n",
    "                d = nums[i] - nums[j]\n",
    "                dp[i][d] += dp[j][d] + 1\n",
    "                if dp[j][d] > 0:\n",
    "                    res += dp[j][d]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\r\n",
    "class Solution:\r\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\r\n",
    "        L=len(nums)\r\n",
    "        ans=0\r\n",
    "        dp=[defaultdict(int) for _ in range(L)]\r\n",
    "        for i in range(L):\r\n",
    "            for j in range(i):\r\n",
    "                diff=nums[i]-nums[j]\r\n",
    "                cnt=dp[j][diff]\r\n",
    "                ans+=cnt\r\n",
    "                dp[i][diff]+=cnt+1\r\n",
    "        return ans\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "\t\tn = len(nums)\n",
    "\t\tif n < 3:\n",
    "\t\t\treturn 0\n",
    "\t\tans = 0\n",
    "\t\t# dp[i][j], i结尾的差值为j的数目\n",
    "\t\t# dp[i][j] = dp[0,i-1][j]+1\n",
    "\t\tdp = [defaultdict(int) for _ in range(n)]\n",
    "\t\tfor i in range(n):\n",
    "\t\t\tfor j in range(i):\n",
    "\t\t\t\td = nums[i] - nums[j]\n",
    "\t\t\t\tans += dp[j][d]\n",
    "\t\t\t\tdp[i][d] += dp[j][d] + 1\n",
    "\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [defaultdict(int) for _ in range(n)]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                d = nums[i] - nums[j]\n",
    "                dp[i][d] += dp[j][d] + 1\n",
    "    \n",
    "\n",
    "        # print(dp)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for v in dp[i].values():\n",
    "                res += v\n",
    "        return res - n*(n-1)//2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import lru_cache\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "\n",
    "\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "\n",
    "        f = [defaultdict(int) for _ in nums]\n",
    "        ans = 0\n",
    "        for i,num in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                d = num-nums[j]\n",
    "                cnt = f[j][d]\n",
    "                ans+=cnt\n",
    "                f[i][d]+=cnt+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [defaultdict(int) for _ in range(n)]\n",
    "        ans = 0\n",
    "        for j in range(1, n):\n",
    "            for i in range(j):\n",
    "                d = nums[j] - nums[i]\n",
    "                dp[j][d] += dp[i][d] + 1\n",
    "                ans += dp[i][d]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        # 2           +0 \n",
    "        # 2, 4        +1 \n",
    "        # 2, 4, 6     +2\n",
    "        # 2, 4, 6, 8  +3 \n",
    "        ans = 0\n",
    "        n = len(nums)\n",
    "        f = [defaultdict(int) for _ in range(n)]\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                d = x - nums[j]\n",
    "                f[i][d] += f[j][d] + 1\n",
    "                ans += f[j][d]\n",
    "                # print(f'i={i},j={j},{f[i]}')\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [collections.defaultdict(int) for _ in range(n)]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                d = nums[i]-nums[j]\n",
    "                dp[i][d] += dp[j][d] + 1\n",
    "                if dp[j][d]:\n",
    "                    res += dp[j][d]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        等差子序列，序列DP问题\n",
    "        f[i][j]代表以nums[i]为结尾，差值为j的子序列个数\n",
    "        f[i][d]=sum([f[j][d] + 1 for j in range(i)]\n",
    "        使用哈希表充当集合，f[i]为一个哈希表，哈希表以{d:cnt},d为差值，cnt为子序列数量\n",
    "        减去长度为2的子序列的个数，从ans中减去\n",
    "        '''\n",
    "        n, res = len(nums), 0\n",
    "        dp =[defaultdict(int) for _ in range(n)]\n",
    "        for i, num in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                d = num - nums[j]\n",
    "                dp[i][d] += dp[j][d] + 1\n",
    "        res += sum([sum([v for _,v in dic.items()]) for dic in dp])\n",
    "        res -= n * (n-1) // 2\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        f = [defaultdict(int) for _ in range(n)]\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i - 1, -1, -1):\n",
    "                d = nums[i] - nums[j]\n",
    "                res += f[j][d]\n",
    "                f[i][d] += f[j][d] + 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        f = [defaultdict(int) for _ in nums]\n",
    "        for i  in range(len(nums)):\n",
    "            for j in range(i):\n",
    "                d = nums[i] - nums[j]\n",
    "                f[i][d] += f[j][d] + 1\n",
    "                ans += f[j][d]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        ans = 0\n",
    "        f = [defaultdict(int) for _ in nums]\n",
    "        for i, x in enumerate(nums):\n",
    "            for j in range(i):\n",
    "                d = x - nums[j]\n",
    "                cnt = f[j][d]\n",
    "                ans += cnt\n",
    "                f[i][d] += cnt + 1\n",
    "            print(f[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [collections.defaultdict(int) for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                dp[i][nums[i] - nums[j]] += dp[j][nums[i] - nums[j]] + 1\n",
    "                ans += dp[j][nums[i] - nums[j]] + 1\n",
    "        return ans - (n - 1) * n // 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        用dp[i]来记录以nums[i]结尾的等差序列的数目(最少长度为2)\n",
    "        当吧nums[i]加在nums[j]后面的时候, 差值已经确定, 可以看dp[j][差值]来计算可以组成多少个新的序列\n",
    "        \n",
    "        '''\n",
    "        N = len(nums)\n",
    "        if N < 3: return 0\n",
    "        \n",
    "        # 记录以 nums[i]结尾的等差序列数目(2个也算)\n",
    "        dp = [defaultdict(int) for _ in range(N)]\n",
    "        \n",
    "        ans = 0\n",
    "        dp[1][nums[1] - nums[0]] = 1\n",
    "\n",
    "        for i in range(2, N):\n",
    "            for j in range(i-1, -1, -1):\n",
    "                \n",
    "                v = dp[j][nums[i]-nums[j]] # 这个差值的序列有多少个\n",
    "                \n",
    "                dp[i][nums[i]-nums[j]] += (v+1) # 和已有的序列组成更长的 + # nums[j] 和 nums[i]组成的序列\n",
    "                \n",
    "                ans += v # 那些长度至少为2的序列 + nums[i]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        用dp[i]来记录以nums[i]结尾的等差序列的数目(最少长度为2)\n",
    "        当吧nums[i]加在nums[j]后面的时候, 差值已经确定, 可以看dp[j][差值]来计算可以组成多少个新的序列\n",
    "        \n",
    "        '''\n",
    "        N = len(nums)\n",
    "        if N < 3: return 0\n",
    "        \n",
    "        # 记录以 nums[i]结尾的等差序列数目(2个也算)\n",
    "        dp = [defaultdict(int) for _ in range(N)]\n",
    "        \n",
    "        ans = 0\n",
    "        dp[1][nums[1] - nums[0]] = 1\n",
    "\n",
    "        for i in range(2, N):\n",
    "            for j in range(i-1, -1, -1):\n",
    "                dp[i][nums[i]-nums[j]] += 1 # nums[j] 和 nums[i]组成的序列\n",
    "                \n",
    "                v = dp[j][nums[i]-nums[j]] # 这个差值的序列有多少个\n",
    "                \n",
    "                dp[i][nums[i]-nums[j]] += v # 和已有的序列组成更长的 + 和最后两个数组成新的序列\n",
    "                \n",
    "                ans += v # 那些长度至少为2的序列 + nums[i]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        2 4 6 8 10\n",
    "        2 6 8 10\n",
    "        6 8 10\n",
    "        \n",
    "        '''\n",
    "        N = len(nums)\n",
    "        if N < 3: return 0\n",
    "        \n",
    "        # 记录以 nums[i]结尾的等差序列数目(2个也算)\n",
    "        dp = [defaultdict(int) for _ in range(N)]\n",
    "        \n",
    "        ans = 0\n",
    "        dp[1][nums[1] - nums[0]] = 1\n",
    "\n",
    "        for i in range(2, N):\n",
    "            for j in range(i-1, -1, -1):\n",
    "                dp[i][nums[i]-nums[j]] += 1 # nums[j] 和 nums[i]组成的序列\n",
    "                \n",
    "                v = dp[j][nums[i]-nums[j]] # 这个差值的序列有多少个\n",
    "                \n",
    "                dp[i][nums[i]-nums[j]] += v # 和已有的序列组成更长的 + 和最后两个数组成新的序列\n",
    "                \n",
    "                ans += v # 那些长度至少为2的序列 + nums[i]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        d=[defaultdict(int) for _ in range(n)]\n",
    "        res=0\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                res+=d[j][nums[i]-nums[j]]\n",
    "                d[i][nums[i]-nums[j]]+=d[j][nums[i]-nums[j]]+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        用dp[i]来记录以nums[i]结尾的等差序列的数目(最少长度为2)\n",
    "        当吧nums[i]加在nums[j]后面的时候, 差值已经确定, 可以看dp[j][差值]来计算可以组成多少个新的序列\n",
    "        \n",
    "        '''\n",
    "        N = len(nums)\n",
    "        if N < 3: return 0\n",
    "        \n",
    "        # 记录以 nums[i]结尾的等差序列数目(2个也算)\n",
    "        dp = [defaultdict(int) for _ in range(N)]\n",
    "        \n",
    "        ans = 0\n",
    "        dp[1][nums[1] - nums[0]] = 1\n",
    "\n",
    "        for i in range(2, N):\n",
    "            for j in range(i-1, -1, -1):\n",
    "                dp[i][nums[i]-nums[j]] += 1 # nums[j] 和 nums[i]组成的序列\n",
    "                \n",
    "                v = dp[j][nums[i]-nums[j]] # 这个差值的序列有多少个\n",
    "                \n",
    "                dp[i][nums[i]-nums[j]] += v # 和已有的序列组成更长的 + 和最后两个数组成新的序列\n",
    "                \n",
    "                ans += v # 那些长度至少为2的序列 + nums[i]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return 0\n",
    "\n",
    "        hash_table = [defaultdict(list) for _ in range(n)]\n",
    "        # print('hash_table:', hash_table)\n",
    "        # print(hash_table[0])\n",
    "        # print('------')\n",
    "        count = 0\n",
    "\n",
    "        for i in range(1, n):\n",
    "            for j in range(i-1, -1, -1):\n",
    "                diff = nums[i] - nums[j]\n",
    "                if hash_table[i][diff]:\n",
    "                    hash_table[i][diff] += (hash_table[j][diff] or 0) + 1\n",
    "                else:\n",
    "                    hash_table[i][diff] = (hash_table[j][diff] or 0) + 1                    \n",
    "                #print(i, j, diff, hash_table)\n",
    "                if hash_table[j][diff] :\n",
    "                    count += hash_table[j][diff] \n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        mp = defaultdict(list)\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            mp[nums[i]].append(i)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(2, n):\n",
    "            for j in range(1, i):\n",
    "                p = nums[j] * 2 - nums[i]\n",
    "                for k in mp[p]:\n",
    "                    if k >= j:\n",
    "                        break\n",
    "                    f[j][i] += f[k][j] + 1\n",
    "                ans += f[j][i]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        mp = defaultdict(list)\n",
    "        for i, x in enumerate(nums):\n",
    "            mp[x].append(i)\n",
    "        # print(f'{mp}')\n",
    "        n = len(nums)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(2, n):\n",
    "            for j in range(1, i):\n",
    "                # print(f'{i,j}')\n",
    "                p = nums[j] * 2 - nums[i]\n",
    "                for k in mp[p]:\n",
    "                    # print(f'{i,j,k}')\n",
    "                    if k >= j:\n",
    "                        continue\n",
    "                    f[j][i] += f[k][j] + 1\n",
    "                ans += f[j][i]\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        mp = defaultdict(list)\n",
    "        for i, x in enumerate(nums):\n",
    "            mp[x].append(i)\n",
    "        n = len(nums)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(2, n):\n",
    "            for j in range(1, i):\n",
    "                p = nums[j] * 2 - nums[i]\n",
    "                for k in mp[p]:\n",
    "                    if k >= j:\n",
    "                        break\n",
    "                    f[j][i] += f[k][j] + 1\n",
    "                ans += f[j][i]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        # 将这个元素和这个元素对应的所有下标绑定起来\n",
    "        hash_ = defaultdict(list)\n",
    "        res = 0\n",
    "        # 固定倒数第二个数\n",
    "        for i in range(1,n-1):\n",
    "            # 保证了最后三个数的等差数列的第一个数一定在j的左边\n",
    "            hash_[nums[i-1]].append(i-1)\n",
    "            # 遍历倒数第一个数\n",
    "            for j in range(i+1,n):\n",
    "                a = nums[i] * 2 -nums[j]\n",
    "                if len(hash_[a]):\n",
    "                    for k in hash_[a]:\n",
    "                        dp[i][j] += dp[k][i] + 1\n",
    "                res += dp[i][j]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        mp = defaultdict(list)\n",
    "        for i, x in enumerate(nums):\n",
    "            mp[x].append(i)\n",
    "        print(f'{mp}')\n",
    "        n = len(nums)\n",
    "        f = [[0] * n for _ in range(n)]\n",
    "        ans = 0\n",
    "        for i in range(2, n):\n",
    "            for j in range(1, i):\n",
    "                print(f'{i,j}')\n",
    "                p = nums[j] * 2 - nums[i]\n",
    "                for k in mp[p]:\n",
    "                    # print(f'{i,j,k}')\n",
    "                    if k >= j:\n",
    "                        continue\n",
    "                    f[j][i] += f[k][j] + 1\n",
    "                ans += f[j][i]\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            d = defaultdict(int)\n",
    "            for j in range(i): # 枚举选哪个\n",
    "                diff = nums[i] - nums[j]\n",
    "                d0 = dfs(j)\n",
    "                nonlocal ans\n",
    "                ans += d0[diff]\n",
    "                d[diff] += d0[diff] + 1\n",
    "            return d\n",
    "        dfs(n-1)\n",
    "        return ans\n",
    "\n",
    "        # n = len(nums)\n",
    "        # ans = 0\n",
    "        # f = [defaultdict(int) for _ in range(n)] # f[i][d]表示选定以nums[i]结尾, 公差为d的且长度>=2的等差序列的数量\n",
    "        # for i, x in enumerate(nums):\n",
    "        #     for j in range(i): # 枚举选哪个\n",
    "        #         diff = x - nums[j]\n",
    "        #         cnt = f[j][diff]\n",
    "        #         ans += cnt # 加上nums[i]能组成长度>=3的子序列\n",
    "        #         f[i][diff] += cnt + 1 # 例如序列0,2,4,6  diff=2时，f的值分别为0,1,2,3\n",
    "        # # for x in f:\n",
    "        # #     print(x)\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfArithmeticSlices(self, A: List[int]) -> int:\n",
    "        from collections import defaultdict\n",
    "        import bisect\n",
    "        n = len(A)\n",
    "        lookup = defaultdict(list)\n",
    "        dp = [defaultdict(int) for _ in range(n)]\n",
    "        res = 0\n",
    "        # 记录每个元素的位置\n",
    "        for idx, val in enumerate(A):\n",
    "            lookup[val].append(idx)\n",
    "        for i in range(n):\n",
    "            for j in range(i):\n",
    "                diff = A[i] - A[j]\n",
    "                target = A[j] - diff\n",
    "                # 先找 和 A[j], A[i]组成三个数组个数\n",
    "                # for idx in lookup[target]:\n",
    "                #     if idx < j:\n",
    "                #         dp[i][diff] += 1\n",
    "                #     else:\n",
    "                #         break\n",
    "                dp[i][diff] += bisect.bisect_left(lookup[target], j) # 可以用二分找个数\n",
    "                # 加上 第j位置公差为diff个数\n",
    "                dp[i][diff] += dp[j][diff]\n",
    "            # 统计个数\n",
    "            for val in dp[i].values():\n",
    "                res += val\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
